package algorithm.middle;

import javax.naming.spi.ObjectFactory;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.middle
 * @Author: 江岸
 * @CreateTime: 2021-04-03 07:57
 * @Description: 1143. 最长公共子序列
 *
 * 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
 *
 * 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 *
 *     例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 *
 * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：text1 = "abcde", text2 = "ace"
 * 输出：3
 * 解释：最长公共子序列是 "ace" ，它的长度为 3 。
 */
public class LongestCommonSubsequence1143 {
    public static void main(String[] args) {
        longestCommonSubsequence("oxcpqrsvwf", "shmtulqrypy" );
    }

    /**
     * 最长公共子序列问题是典型的二维动态规划问题。
     *
     * 假设字符串 text1\textit{text}_1text1​ 和 text2\textit{text}_2text2​ 的长度分别为 mmm 和 nnn，创建 m+1m+1m+1 行 n+1n+1n+1 列的二维数组 dp\textit{dp}dp，其中 dp[i][j]\textit{dp}[i][j]dp[i][j] 表示 text1[0:i]\textit{text}_1[0:i]text1​[0:i] 和 text2[0:j]\textit{text}_2[0:j]text2​[0:j] 的最长公共子序列的长度。
     *
     *     上述表示中，text1[0:i]\textit{text}_1[0:i]text1​[0:i] 表示 text1\textit{text}_1text1​ 的长度为 iii 的前缀，text2[0:j]\textit{text}_2[0:j]text2​[0:j] 表示 text2\textit{text}_2text2​ 的长度为 jjj 的前缀。
     *
     * 考虑动态规划的边界情况：
     *
     *     当 i=0i=0i=0 时，text1[0:i]\textit{text}_1[0:i]text1​[0:i] 为空，空字符串和任何字符串的最长公共子序列的长度都是 000，因此对任意 0≤j≤n0 \le j \le n0≤j≤n，有 dp[0][j]=0\textit{dp}[0][j]=0dp[0][j]=0；
     *
     *     当 j=0j=0j=0 时，text2[0:j]\textit{text}_2[0:j]text2​[0:j] 为空，同理可得，对任意 0≤i≤m0 \le i \le m0≤i≤m，有 dp[i][0]=0\textit{dp}[i][0]=0dp[i][0]=0。
     *
     * 因此动态规划的边界情况是：当 i=0i=0i=0 或 j=0j=0j=0 时，dp[i][j]=0\textit{dp}[i][j]=0dp[i][j]=0。
     *
     * 当 i>0i>0i>0 且 j>0j>0j>0 时，考虑 dp[i][j]\textit{dp}[i][j]dp[i][j] 的计算：
     *
     *     当 text1[i−1]=text2[j−1]\textit{text}_1[i-1]=\textit{text}_2[j-1]text1​[i−1]=text2​[j−1] 时，将这两个相同的字符称为公共字符，考虑 text1[0:i−1]\textit{text}_1[0:i-1]text1​[0:i−1] 和 text2[0:j−1]\textit{text}_2[0:j-1]text2​[0:j−1] 的最长公共子序列，再增加一个字符（即公共字符）即可得到 text1[0:i]\textit{text}_1[0:i]text1​[0:i] 和 text2[0:j]\textit{text}_2[0:j]text2​[0:j] 的最长公共子序列，因此 dp[i][j]=dp[i−1][j−1]+1\textit{dp}[i][j]=\textit{dp}[i-1][j-1]+1dp[i][j]=dp[i−1][j−1]+1。
     *
     *     当 text1[i−1]≠text2[j−1]\textit{text}_1[i-1] \ne \textit{text}_2[j-1]text1​[i−1]​=text2​[j−1] 时，考虑以下两项：
     *
     *         text1[0:i−1]\textit{text}_1[0:i-1]text1​[0:i−1] 和 text2[0:j]\textit{text}_2[0:j]text2​[0:j] 的最长公共子序列；
     *
     *         text1[0:i]\textit{text}_1[0:i]text1​[0:i] 和 text2[0:j−1]\textit{text}_2[0:j-1]text2​[0:j−1] 的最长公共子序列。
     *
     *     要得到 text1[0:i]\textit{text}_1[0:i]text1​[0:i] 和 text2[0:j]\textit{text}_2[0:j]text2​[0:j] 的最长公共子序列，应取两项中的长度较大的一项，因此 dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1])\textit{dp}[i][j]=\max(\textit{dp}[i-1][j],\textit{dp}[i][j-1])dp[i][j]=max(dp[i−1][j],dp[i][j−1])。
     *
     * 由此可以得到如下状态转移方程：
     *
     * dp[i][j]={dp[i−1][j−1]+1,text1[i]=text2[j]max⁡(dp[i−1][j],dp[i][j−1]),text1[i]≠text2[j]\textit{dp}[i][j] = \begin{cases} \textit{dp}[i-1][j-1]+1, & \textit{text}_1[i]=\textit{text}_2[j] \\ \max(\textit{dp}[i-1][j],\textit{dp}[i][j-1]), & \textit{text}_1[i] \ne \textit{text}_2[j] \end{cases} dp[i][j]={dp[i−1][j−1]+1,max(dp[i−1][j],dp[i][j−1]),​text1​[i]=text2​[j]text1​[i]​=text2​[j]​
     *
     * 最终计算得到 dp[m][n]\textit{dp}[m][n]dp[m][n] 即为 text1\textit{text}_1text1​ 和 text2\textit{text}_2text2​ 的最长公共子序列的长度。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/longest-common-subsequence/solution/zui-chang-gong-gong-zi-xu-lie-by-leetcod-y7u0/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    //动态规划，二维数组
    public  static int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for (int i=1;i<=text1.length();i++){
            char c = text1.charAt(i-1);
            for (int j=1;j<=text2.length();j++){
                char b = text2.charAt(j-1);
                if (c==b){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }

}
